/**
 回溯
 * @param {number[]} matchsticks
 * @return {boolean}
 */
export var makesquare = function (matchsticks) {
  if (matchsticks.length < 4) return false
  let sum = matchsticks.reduce((a, b) => a + b, 0)
  if (sum % 4 !== 0) return false
  const avg = sum / 4
  matchsticks.sort((a, b) => b - a)
  const edges = new Array(4).fill(0)
  return dfs(0, matchsticks, edges, avg)
}

/**
 * @param {number} idx 当前检到的火柴的下标
 * @param {number[]} matchsticks 火柴列表
 * @param {number[]} edges 边状态
 * @param {number} avg 单边长度
 */
function dfs(idx, matchsticks, edges, avg) {
  if (idx === matchsticks.length) return true
  for (let i = 0; i < edges.length; i++) {
    // 把数填到第i条边上
    edges[i] += matchsticks[idx]
    // 如果第一条边未放满，继续历遍放满则开始放下一边
    if (edges[i] <= avg && dfs(idx + 1, matchsticks, edges, avg)) return true
    edges[i] -= matchsticks[idx]
  }
  return false
}

/**
 * 状态压缩 + 动态规划
 * @param {number[]} matchsticks
 * @return {boolean}
 */
export var makesquare2 = function (matchsticks) {
  const totalLen = matchsticks.reduce((a, b) => a + b, 0)
  if (totalLen % 4 !== 0) {
    return false
  }
  const len = Math.floor(totalLen / 4),
    n = matchsticks.length
  const dp = new Array(1 << n).fill(-1)
  dp[0] = 0
  for (let s = 1; s < 1 << n; s++) {
    for (let k = 0; k < n; k++) {
      if ((s & (1 << k)) === 0) {
        continue
      }
      const s1 = s & ~(1 << k)
      if (dp[s1] >= 0 && dp[s1] + matchsticks[k] <= len) {
        dp[s] = (dp[s1] + matchsticks[k]) % len
        break
      }
    }
  }
  return dp[(1 << n) - 1] === 0
}
